//空间优化
class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int sum = 0;
        for (auto& i : nums)
            sum += i;
        if (sum % 2)
            return false;

        int n = nums.size(), target = sum / 2;
        vector<bool> dp(target + 1, false);
        dp[0] = true;

        for (int i = 1; i < n + 1; i++)
            for (int j = target; j >= nums[i - 1]; j--)
                if (dp[j - nums[i - 1]])
                    dp[j] = true;

        return dp[target];
    }
};

//dp[i][j]表示：考虑前i个数字，是否有选法，可以使得和等于j
// class Solution {
// public:
//     bool canPartition(vector<int>& nums) {
//         int sum = 0;
//         for (auto& i : nums)
//             sum += i;

//         if (sum % 2)
//             return false;

//         int n = nums.size(), target = sum / 2;
//         vector<vector<bool>> dp(n + 1, vector<bool>(target + 1, true));
//         for (int i = 1; i < target + 1; i++)
//             dp[0][i] = false;

//         for (int i = 1; i < n + 1; i++)
//         {
//             for (int j = 1; j < target + 1; j++)
//             {
//                 if (j - nums[i - 1] >= 0 && dp[i - 1][j - nums[i - 1]])
//                     dp[i][j] = true;
//                 else
//                     dp[i][j] = dp[i - 1][j];
//             }
//         }
//         return dp[n][target];
//     }
// };



